/*
  城市交通路网
 【题目描述】
    下表表示城市之间的交通路网。其中A/B1/B2/B3/C1/C2/C3/D1/D2/E均代表城市，
    表中描叙了2个城市之间所有可以单向通行的所有线路, 例如:
      "A -> B1 油费2元"表示可以单向从城市A到达城市B1，通行费用为2元油费。
      表中未描叙的则表示不可达的路线。
    根据路网表我们可以知道, 如果要单向从城市A到城市E，不能直接到达，需要经过其它城市中转。

      A -> B1 油费2元   B1 -> C1 油费12元   C1 -> D1 油费3元   D1 -> E 油费5元
      A -> B2 油费5元   B1 -> C2 油费14元   C1 -> D2 油费9元   D2 -> E 油费2元
      A -> B3 油费1元   B2 -> C1 油费6元    C2 -> D1 油费6元
                        B2 -> C2 油费10元   C2 -> D2 油费5元
                        B2 -> C3 油费4元    C3 -> D2 油费10元
                        B3 -> C1 油费13元
                        B3 -> C2 油费12元
                        B3 -> C3 油费11元

    如果要单向从城市 A 通行到 E, 请用动态规划的最优化原理求出 A -> E 的最省费用及对应的路径。
 【输入】
    第一行为城市的数量N;
    后面是 N*N 的表示两个城市间费用组成的矩阵。
    说明: N个城市分别用 1~N 进行编码, 其中, 1对应城市A，N对应城市E。
         矩阵的第一行表示从 1 号城市出发，分别到达 列数代表的城市的费用，依次类推。
         如：矩阵中第1行第2列的数表示单向从1号城市出发到达2号城市的费用；
            如果不可能达，则费用为0, 如单向从1号城市无法直接到达N号城市，所以第1行第N列的数为0。
 【输出】
    共输出2行，第一行为从 A 到 E 的最省费用。
    第二行为若干个整数，每个整数表示每一步到达第几号城市，假设第一个数为2则表示第一步到2号城市，
        整数与整数之间用空格隔开。
 【输入样例】
    10
    0  2  5  1  0  0  0  0  0  0
    0  0  0  0 12 14  0  0  0  0
    0  0  0  0  6 10  4  0  0  0
    0  0  0  0 13 12 11  0  0  0
    0  0  0  0  0  0  0  3  9  0
    0  0  0  0  0  0  0  6  5  0
    0  0  0  0  0  0  0  0 10  0
    0  0  0  0  0  0  0  0  0  5
    0  0  0  0  0  0  0  0  0  2
    0  0  0  0  0  0  0  0  0  0
 【输出样例】
    19
    1 3 5 8 10
*/